﻿namespace AStartAlgorithm.Comm
{

    /// <summary>
    /// A星算法
    /// </summary>
    public class AStartServer
    {
        int[,] Map;
        List<UnitPonit> openList = new List<UnitPonit>();
        List<UnitPonit> closeList = new List<UnitPonit>();
        UnitPonit start_point;
        UnitPonit end_point;

        public AStartServer(int[,] map)
        {
            Map = map;
            int col = map.GetLength(0);
            int row = map.GetLength(1);
            for (int x = 0; x < col; x++)
            {
                for (int y = 0; y < row; y++)
                {
                    if (Map[x, y] == (int)MapType.Star)
                    {
                        start_point = new UnitPonit(x, y);
                    }
                    if (Map[x, y] == (int)MapType.End)
                    {
                        end_point = new UnitPonit(x, y);
                    }
                }
            }

            var data = ArrayParse.Arr2RowT(Map).ToList();
            if (data.Count(t => t == (int)MapType.Star) != 1)
                throw new Exception("需设置1个起点");
            if (data.Count(t => t == (int)MapType.End) != 1)
                throw new Exception("需设置1个终点");
        }

        public List<UnitPonit> Compute()
        {
            //计算权重
            //F=G（A点到指定点的代价）+H（估算的成本，行列的差值）
            closeList.Add(start_point);//添加第一个闭合列表，起点
            GetLocation(start_point);

            //全部找完，closelist结尾为终点则找到路径
            var lastPonit = closeList[closeList.Count - 1];
            if (lastPonit.id != end_point.id) throw new Exception("无法到达终点！");

            //然后追溯路径
            List<UnitPonit> resPonit = new List<UnitPonit>();
            GetResPonit(lastPonit, resPonit);
            return resPonit;
        }

        private void GetResPonit(UnitPonit lastPonit, List<UnitPonit> resPonit)
        {
            resPonit.Add(lastPonit);
            var parePonit = closeList.Where(t => t.id == lastPonit.parentId).FirstOrDefault();
            if (parePonit != null && parePonit.id != start_point.id)
            {
                GetResPonit(parePonit, resPonit);
            }
        }

        /// <summary>
        /// 获取临近路径
        /// </summary>
        /// <param name="start_point"></param>                       
        private void GetLocation(UnitPonit start_point)
        {
            int x = start_point.x;
            int y = start_point.y;
            //处理边界
            if (x > 0)
                AddData(x - 1, y, 10, start_point.id);
            if (x < Map.GetLength(0) - 1)
                AddData(x + 1, y, 10, start_point.id);
            if (y > 0)
                AddData(x, y - 1, 10, start_point.id);
            if (y < Map.GetLength(1) - 1)
                AddData(x, y + 1, 10, start_point.id);

            //获取最优解，然后加入closelist，移除openlist。相同则以后面的优先。          
            int minValue = 0;
            int best_index = -1;
            for (int i = openList.Count - 1; i >= 0; i--)
            {
                if (best_index == -1)
                {
                    minValue = openList[i].value;
                    best_index = i;
                }
                else
                {
                    if (minValue > openList[i].value)
                    {
                        minValue = openList[i].value;
                        best_index = i;
                    }
                }
            }
            //设置队列
            if (best_index >= 0)
            {
                var bestPoint = openList[best_index];
                closeList.Add(bestPoint);
                openList.RemoveAt(best_index);

                if (bestPoint.id != end_point.id)
                {
                    GetLocation(bestPoint);
                }
            }
        }

        private void AddData(int x, int y, int g, string parentId)
        {
            //墙不做处理
            if (Map[x, y] != (int)MapType.Empty && Map[x, y] != (int)MapType.End) return;

            UnitPonit point = new UnitPonit(x, y);
            point.parentId = parentId;
            point.h = Math.Abs(end_point.x - x) * 10 + Math.Abs(end_point.y - y) * 10;
            point.g = g;

            //已加入到闭合列表不处理
            if (closeList.Any(t => t.id == point.id)) return;

            //添加到开放列表
            if (!openList.Any(t => t.id == point.id))
            {
                openList.Add(point);
                Map[x, y] = point.value;
            }
        }
    }


    public class UnitPonit
    {
        public UnitPonit(int x, int y)
        {
            this.x = x;
            this.y = y;
            id = $"{x}_{y}";
        }

        public string? parentId { get; set; }

        /// <summary>
        /// 位置x
        /// </summary>
        public int x { get; set; }

        /// <summary>
        /// 位置y
        /// </summary>
        public int y { get; set; }

        /// <summary>
        /// id
        /// </summary>
        public string id { get; set; }

        /// <summary>
        /// f值，越小说明成本越低
        /// </summary>
        public int value => h + g;

        /// <summary>
        /// 曼哈顿距离
        /// </summary>
        public int h { get; set; }

        /// <summary>
        /// 移动的代价
        /// </summary>
        public int g { get; set; }
    }
}
